package org.zxp.datastructure.tree;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.CountDownLatch;

/**
 * @program: effectiveJava
 * @description: 大顶堆 left:i*2   right:i*2 + 1
 * @author: X-Pacific zhang
 * @create: 2019-08-06 16:51
 **/
public class Heap {
    private int[] arr;//堆使用数组构建的
    private int max;//数组的长度
    private int count;//当前堆已经存储了多少元素

    public Heap() {
        this.max = 64;
        count = 0;
        arr = new int[max];
    }

    @Test
    public void testInsert() {
        Heap heap = new Heap();
        heap.insert(33).insert(27).insert(21).insert(16).insert(13).insert(15).insert(9)
                .insert(5).insert(6).insert(7).insert(8).insert(1).insert(2);
        for (int i = 0; i <= heap.count; i++) {
            System.out.print(heap.arr[i] + ",");
        }
        System.out.println();
        heap.insert(22);
        for (int i = 0; i <= heap.count; i++) {
            System.out.print(heap.arr[i] + ",");
        }
    }

    /**
     * 再堆中插入元素，也支持没数据时重新建堆
     * 插入数组末尾，向上找比他小的元素就交换，直到找不到（大顶堆）
     *
     * @param val
     * @return
     */
    public Heap insert(int val) {
        if (count == max) {
            return null;
        }
        int p = ++count;
        while (true) {
            int pp = p / 2;
            arr[p] = val;
            int parent = arr[pp];
            if (pp == 0) break;
            if (parent < val) {
                arr[pp] = arr[p];
                arr[p] = parent;
                p = pp;
            } else {
                break;
            }
        }
        return this;
    }

    @Test
    public void testDel() {
        int[] arr2 = getArr(33, 27, 21, 16, 13, 15, 19, 5, 6, 7, 8, 1, 2, 12);
        int top = deleteTop(arr2, arr2.length - 1);
        System.out.println("删除了" + top);
        for (int i = 0; i < arr2.length; i++) {
            System.out.print(arr2[i] + ",");
        }
    }

    public int[] getArr(int... num) {
        int length = num.length + 1;
        int[] arr2 = new int[length];
        for (int i = 0; i < num.length; i++) {
            arr2[i + 1] = num[i];
        }
        return arr2;
    }

    /**
     * 从堆中删除堆顶元素
     *
     * @return
     */
    public int deleteTop(int[] arr2, int n) {
        int top = arr2[1];//堆顶元素
        swap(arr2, 1, n);
        arr2[n--] = 0;
        int p = 1;
        heapit(arr2, n, p);
        return top;
    }


    /**
     * 从上（下标为p的元素）向下进行堆化
     * 把某一个不符合堆特性的节点进行堆化（移动位置，使其成为一个合格的堆）
     *
     * @param arr2 需要堆化的数组
     * @param n    数组内有效数据的个数
     * @param p    需要开始堆化的节点
     */
    public void heapit(int[] arr2, int n, int p) {
        while (true) {
            int maxPos = p;
            if (p * 2 <= n && arr2[p] < arr2[p * 2]) maxPos = p * 2;
            if (p * 2 + 1 <= n && arr2[maxPos] < arr2[p * 2 + 1]) maxPos = p * 2 + 1;
            if (maxPos == p) break;
            swap(arr2, p, maxPos);
            p = maxPos;
        }
    }

    /**
     * 下标为a的替换成下标b的
     *
     * @param a
     * @param b
     */
    public void swap(int[] arr2, int a, int b) {
        int tmp = arr2[a];
        arr2[a] = arr2[b];
        arr2[b] = tmp;
    }


    @Test
    public void testMakeheap() {
        int[] arr2 = getArr(7, 5, 19, 8, 4, 1, 20, 13, 16);
        makeMaxHeap(arr2, arr2.length - 1);
        for (int i = 0; i < arr2.length; i++) {
            System.out.print(arr2[i] + ",");
        }
    }

    /**
     * 改变普通数组为堆
     * 从第一个不是叶子节点的节点开始
     *
     * @param arr2
     * @param n
     */
    public void makeMaxHeap(int[] arr2, int n) {
        for (int i = n / 2; i > 0; i--) {
            heapit(arr2, n, i);
        }
    }

    @Test
    public void testSort() {
        int[] arr2 = getArr(9, 6, 3, 1, 5);
        heapsort(arr2, 5);
        for (int i : arr2) {
            System.out.println(i);
        }
    }

    /**
     * 对arr2进行排序，n为数据个数
     *
     * @param arr2
     * @param n
     */
    public void heapsort(int[] arr2, int n) {
        makeMaxHeap(arr2, n);//原地建堆
        int k = n;
        while (k > 1) {
            swap(arr2, 1, k);//将堆顶元素(最大值)交换至素组末尾
            k--;
            heapit(arr2, k, 1);//对新的堆顶进行堆化
        }
    }

    /**
     * 小顶堆从上（下标为p的元素）向下进行堆化
     *
     * @param arr2
     * @param n
     * @param p
     */
    public void heapHead(Element[] arr2, int n, int p) {
        while (true) {
            int minpox = p;
            if (p * 2 <= n && arr2[p].getVal() > arr2[p * 2].getVal()) minpox = p * 2;
            if (p * 2 + 1 <= n && arr2[minpox].getVal() > arr2[p * 2 + 1].getVal()) minpox = p * 2 + 1;
            if (minpox == p) break;
            Element tmp = arr2[p];
            arr2[p] = arr2[minpox];
            arr2[minpox] = tmp;
            p = minpox;
        }
    }

    /**
     * 小顶堆从上（下标为p的元素）向下进行堆化
     *
     * @param arr2
     * @param n
     * @param p
     */
    public void heapHead2(int[] arr2, int n, int p) {
        while (true) {
            int minpox = p;
            if (p * 2 <= n && arr2[p] > arr2[p * 2]) minpox = p * 2;
            if (p * 2 + 1 <= n && arr2[minpox] > arr2[p * 2 + 1]) minpox = p * 2 + 1;
            if (minpox == p) break;
            int tmp = arr2[p];
            arr2[p] = arr2[minpox];
            arr2[minpox] = tmp;
            p = minpox;
        }
    }


    /**
     * 从堆中删除小顶堆堆顶元素，并返回构建对象
     *
     * @return
     */
    public Element deleteMinTop(Element[] arr2, int n) {
        Element top = arr2[1];//堆顶元素
        arr[1] = arr[n];
        arr[n--] = 0;
        heapHead(arr2, n, 1);
        return top;
    }

    /**
     * 改变普通数组为堆，小顶堆
     * 从第一个不是叶子节点的节点开始
     *
     * @param arr2
     * @param n
     */
    public void makeMinHeap(Element[] arr2, int n) {
        for (int i = n / 2; i > 0; i--) {
            heapHead(arr2, n, i);
        }
    }

    /**
     * 改变普通数组为堆，小顶堆
     * 从第一个不是叶子节点的节点开始
     *
     * @param arr2
     * @param n
     */
    public void makeMinHeap2(int[] arr2, int n) {
        for (int i = n / 2; i > 0; i--) {
            heapHead2(arr2, n, i);
        }
    }

    //以O(n*logn)的时间复杂度通过快排（并发排序）+堆排序（汇总排序）针对分布式存储数据全排序的粗浅算法思路
    @Test
    public void testMergeAllArray() throws InterruptedException {
        int[] arr1 = {2, 5, 7, 9, 6, 8, 2, 4, 3};
        int[] arr2 = {115, 55, 93};
        int[] arr3 = {23, 98, 11, 234};
        int[] arr4 = {9, 5, 7};
        int[] arr5 = {2345, 3, 99999};
        int[] arr6 = {12, 45, 67};
        int[] arr7 = {8888, 5, 4567};
        List<int[]> list = Arrays.asList(arr1, arr2, arr3, arr4, arr5, arr6, arr7);
        CountDownLatch countDownLatch = new CountDownLatch(list.size());
        list.forEach(o -> {
            new Thread(() -> {
                QuickSort.sort(o);
                countDownLatch.countDown();
            }).start();
        });
        countDownLatch.await();
        List result = new ArrayList(64);
        Element[] elements = new Element[list.size() + 1];
        elements[0] = new Element(0, 0);
        int[] indexs = new int[list.size()];//保存每个数组已经遍历到的下标
        for (int i = 0; i < list.size(); i++) { //遍历每个数组，并取出当前数组最小值
            elements[i + 1] = new Element(i, list.get(i)[0]);//将每个数组的最小值放入临时处理数组
        }
        makeMinHeap(elements, list.size());//对数组进行小顶堆构建
        while (true) {
            heapHead(elements, list.size(), 1);//对堆顶元素进行堆化logn
            int arrno = elements[1].getArrno();
            int limit = 0;
            boolean ready2exit = false;
            while (indexs[arrno] + 1 == list.get(arrno).length) {//当前数组已经遍历完毕，取下一个数组
                if (++limit == list.size()) {
                    ready2exit = true;
                    break;
                }//全部数据遍历完毕，准备退出
                if (arrno == list.size() - 1) {
                    arrno = 1;
                } else {
                    arrno++;
                }
            }
            if (ready2exit) {//没有更新的数据放入数组，直接对堆剩余数据做堆排序
                int k = elements.length - 1;
                while (k > 1) {
                    Element tmp = elements[1];
                    elements[1] = elements[k];
                    elements[k] = tmp;
                    heapHead(elements, --k, 1);
                }
                for (int i = elements.length - 1; i > 0; i--) {
                    result.add(elements[i].getVal());
                }
                break;
            }
            result.add(elements[1].getVal());//将最小值加入最终排序结果中
            elements[1] = new Element(arrno, list.get(arrno)[++indexs[arrno]]);//将堆顶元素替换
        }
        result.forEach(o -> System.out.print(o + ","));
    }


    static class QuickSort {
        public static void sort(int[] a) {
            sort(a, 0, a.length - 1);
        }

        public static void main(String[] args) {
            int[] arr1 = {2, 5, 7, 9, 6, 8, 2, 4, 3};
            sort(arr1);
            for (int i = 0; i < arr1.length; i++) {
                System.out.println(arr1[i]);
            }
        }

        private static void sort(int[] a, int p, int r) {
            if (p >= r) {
                return;
            }
            int q = partition(a, p, r);//获取一个点并获取此点的下标
            sort(a, p, q - 1);//对q点的前半段进行快排 q点相当于已经排好
            sort(a, q + 1, r);//队q点的后半段进行快拍
        }


        private static int partition(int[] a, int p, int r) {
            int i = p, j = p;//i-1为已经排好的范围，j为遍历的游标
            int pivot = a[r];//以最末尾的点为分界点
            while (true) {//并将大于此点的数据移动到右边，小于此点的数据移动到左边
                if (j == r) {//当遍历的游标到了数组末尾则把i的位置与末尾元素互换，并返回下标作为q点下标
                    int tmp = a[i];
                    a[i] = a[r];
                    a[r] = tmp;
                    return i;
                }
                if (a[j] <= pivot) {//如果小于末尾值，则i，j交换
                    int tmp = a[i];
                    a[i++] = a[j];
                    a[j] = tmp;
                }//移动下标
                j++;
            }
        }
    }

    static class Element {
        int arrno;//数组序号
        int val;//值

        public Element(int arrno, int val) {
            this.arrno = arrno;
            this.val = val;
        }

        public int getArrno() {
            return arrno;
        }

        public void setArrno(int arrno) {
            this.arrno = arrno;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return "Element{" +
                    "arrno=" + arrno +
                    ", val=" + val +
                    '}';
        }
    }
}
